UVa/929 - Number Maze/929.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <sstream>
   6 #include <fstream>
   7 #include <cassert>
   8 #include <climits>
   9 #include <cstdlib>
  10 #include <cstring>
  11 #include <string>
  12 #include <cstdio>
  13 #include <vector>
  14 #include <cmath>
  15 #include <queue>
  16 #include <deque>
  17 #include <stack>
  18 #include <map>
  19 #include <set>
  20
  21 #define D(x) cout << #x " is " << x << endl
  22 const int MAXN = 1000, MAXEDGE = 10;
  23 int g[MAXN][MAXN], d[MAXN][MAXN];
  24 int rows, cols;
  25
  26 struct state{
  27   int i, j, w;
  28 };
  29
  30
  31 queue<state> q[MAXEDGE];
  32 int current_q;
  33
  34 void enqueue(int i, int j, int w){
  35   q[w % MAXEDGE].push((state){i, j, w});
  36 }
  37
  38 bool dequeue(int &i, int &j, int &w){
  39   int started_at = current_q;
  40   while (q[current_q].empty()){
  41     current_q = (current_q + 1)%MAXEDGE;
  42     if (current_q == started_at) return false;
  43   }
  44   const state &s = q[current_q].front();
  45   i = s.i, j = s.j, w = s.w;
  46   q[current_q].pop();
  47   return true;
  48 }
  49
  50 int dijkstra(){
  51   //clean queues
  52   for (int i=0; i<MAXEDGE; ++i){
  53     for (; q[i].size(); q[i].pop());
  54   }
  55   current_q = g[0][0];
  56   d[0][0] = g[0][0];
  57   enqueue(0, 0, g[0][0]);
  58   for (int i, j, w; dequeue(i, j, w); ){
  59     //printf("popped (%d, %d, %d)\n", i, j, w);
  60     if (w > d[i][j]) continue;
  61     if (i == rows-1 && j == cols-1) break;
  62     for (int di=-1; di<=1; ++di){
  63       for (int dj=-1; dj<=1; ++dj){
  64         if (di != 0 ^ dj != 0){
  65           int ni = i + di;
  66           int nj = j + dj;
  67           if (0 <= ni && ni < rows && 0 <= nj && nj < cols){
  68             int w_extra = g[ni][nj];
  69             if (w + w_extra < d[ni][nj]){
  70               d[ni][nj] = w + w_extra;
  71               enqueue(ni, nj, w + w_extra);
  72             }
  73           }
  74         }
  75       }
  76     }
  77   }
  78   return d[rows-1][cols-1];
  79 }
  80
  81 int main(){
  82   int how_many;
  83   for (scanf("%d", &how_many); how_many--; ){
  84     scanf("%d %d", &rows, &cols);
  85     for (int i=0; i<rows; ++i){
  86       for (int j=0; j<cols; ++j){
  87         scanf("%d", &g[i][j]);
  88
  89         //cleaning
  90         d[i][j] = INT_MAX;
  91       }
  92     }
  93
  94     printf("%d\n", dijkstra());
  95   }
  96   return 0;
  97 }